package airthmetic.exercise.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class _144_二叉树的前序遍历 {
    // 递归写法
    public static List<Integer> preorderTraversal(TreeNode root) {
        if(root == null){
            return new ArrayList<Integer>();
        }
        List<Integer> list = new ArrayList();
        recur(root, list);

        return list;
    }
    // 递归写法
    public static void recur(TreeNode node, List<Integer> list){
        // terminal
        if(node==null){
            return;
        }
        // process current logic
        list.add(node.val);
        recur(node.left,list);
        recur(node.right,list);
    }


    // 遍历写法
    public static List<Integer> preorderTraversal2(TreeNode root) {
        if(root == null){
            return new ArrayList<Integer>();
        }
        // 遍历写法 借助一个栈 将根节点遍历之前放入栈内，遍历内弹出栈顶元素，放入最终返回集合中
        // 判断弹出元素是否包含左右子节点，如果包含先将右节点压入栈内 (模拟栈，利用后进先出)
        // 再压入左子节点 再循环执行直到栈内元素为空
        LinkedList<TreeNode> stack = new LinkedList();
        stack.push(root);

        List<Integer> res = new ArrayList();
        while(!stack.isEmpty()){
            TreeNode n = stack.pop();
            res.add(n.val);

            if(n.right != null){
                stack.push(n.right);
            }
            if(n.left != null){
                stack.push(n.left);
            }
        }

        return res;
    }
    public static void main(String[] args) {
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode = new TreeNode(1, treeNode2, treeNode3);
        System.out.println(treeNode);

        System.out.println(preorderTraversal(treeNode));
        System.out.println(preorderTraversal2(treeNode));
    }
}
